V polovině 13. století při založení královského města Kolín byl zřejmě založen i kostel, z něhož se chrám vyvinul do současné podoby. Zakladatelem byl nejspíše král Přemysl Otakar II. Stavba byla dokončena před rokem 1300 vybudováním dvou štíhlých osmibokých věží na západním průčelí.
Za vlády Karla IV. prodělo město Kolín požár, během kterého byl poškozen také kostel, který následně prošel přestavbou. Petr Parléř tehdy v letech 1360 - 1379 vybudoval nový gotický chór, byla rozšířena okna v trojlodí a proběhla také přístavba kaple Panny Marie. Petr Parléř tedy v Kolíně zahájil výstavbu nového, vysokého chóru na místě původního presbytáře. Obnovený chrám byl vysvěcen roku 1378. Vlastní kostel je trojlodní stavba, postavená v gotickém slohu. Nižší, západní část je raně gotická s vnějším opěrným systémem. Na severní straně se nacházejí dva vstupní portály. Tympanon pravého portálu je kopií původní plastiky ze 13. století, která byla sňata při rekonstrukci na konci 19. století.
Ke konci 15. století byly západní věže opatřeny věžemi ve tvaru jehlanu a nárožní věžičky. Roku 1643 kostel rabovala švédská vojska a značně jej poškodila. Další pohroma měla podobu požáru, který kostel poškodil roku 1976. Generální rekonstrukce pak proběhla v polovině 19. století, jenomže záhy, roku 1869, přišel další ničivý požár. Další rekonstrukce je vedena Josefem Mockerem, který nejdříve přestavil severní věž a zvonici, poté rekonstruuje i Parléřovu práci - chór, kde řadu architektonických prvků buď doplnil a nebo zcela vyměnil. Zastřešení katedrály také pochází z 19. století.
Poslední ránu tomuto architektonickému skvostu zasadila 2. světová válka. Při jednom z náletu na město byl v roce 1945 chrám zasažen bombou. Opravy byly zahájeny až v roce 1963 a de facto trvají do současnosti. Za podrobnější zmínku stojí samostatná zvonice. V jejím nejvyšším patře se nachází bývalý byt hlásného s ochozem. V nižším patře je zavěšeno pět zvonů. Původních šest zvonů z roku 1797 bylo zabaveno Němci za 2. světové války. Zvony byly roztaveny a a použity pro výrobu zbraní. Současné zvony tedy již nejsou původní.
Zvony Sanktusník a Václav pocházejí z kostela sv. Víta na Zálabí a byly po válce umístěny v Kolíně. Zvon Kohoutek pravděpodobně pochází z městského popraviště. Zvony Bartoloměj a Jan Pavel jsou úplně nové, jelikož byly odlity v roce 2000.
Jako veliká zajímavost je to, že blízkosti Parléřova chóru se na místě dřívější hradební bašty nachází barokní kostnice.